#include <iostream>
#include <chrono>
#include <string>
#include "util/testharness.h"
#include "pure_mem/rowex/art_tree.h"
#include "pure_mem/rowex/art_key.h"

using namespace art_rowex;

namespace rocksdb {
        void loadKey(TID tid, Key &key) {
            // Store the key of the tuple into the key vector
            // Implementation is database specific
            key.setKeyLen(sizeof(tid));
            reinterpret_cast<uint64_t *>(&key[0])[0] = __builtin_bswap64(tid);
        }


        struct KV_Pair{
            char key[10];
            char value[10];
        };

        TID genKVWithNUm(int n){
            KV_Pair* ret = new KV_Pair();
            if (n < 0){
                ret->key[0] = 0;
                ret->value[0] = 'n';
                ret->value[1] = 'i';
                ret->value[2] = 'l';
                ret->value[3] = 0;
            }else{
                std::string str = std::to_string(n);
                memcpy(ret->key, str.c_str(), str.length());
                memcpy(ret->value, str.c_str(), str.length());
            }
            return (TID)(ret);
        }

        void loadKeyFromTid(TID tid, Key &key){
            KV_Pair* kv = (KV_Pair*)(tid);
            key.set(kv->key, strlen(kv->key));
        }

        void printTID(TID tid){
            if (tid == 0) {
                std::cout << "printTID--------current tid is empty." << std::endl;
            }else{
                KV_Pair* kv = (KV_Pair*)(tid);
                std::cout << "printTID--------key: " << kv->key << ", value: " << kv->value << std::endl;
            }
        }

    class ROWEXExample{
        public:
        

        void assertWithKey(TID t, int num){
            if (t == 0){
                std::cout << "error: t is empty for key " << num << std::endl;
                exit(0);
            }
            
            TID a = genKVWithNUm(num);
            Key aKey, bKey;
            loadKeyFromTid(a, aKey);
            loadKeyFromTid(t, bKey);
            std::cout << "assertWithKey  a:" << std::endl;
            aKey.dump();
            bKey.dump();

            assert(aKey.getKeyLen() == bKey.getKeyLen());
            for (uint32_t i = 0; i < std::min(aKey.getKeyLen(), bKey.getKeyLen()); i++){
                assert(aKey[i] == bKey[i]);
            }
        }
        
        void insertWithNum(art_rowex::Tree &tree, int num){
            TID a = genKVWithNUm(num);
            Key curKey;
            loadKeyFromTid(a, curKey);
            TID cur,next;
            tree.insertOrGetLG(curKey, a, cur, next);
            std::cout<< "----------a: "<< a << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a);
        }

        TID searchWithNum(art_rowex::Tree &tree, int num){
            TID a = genKVWithNUm(num);
            Key curKey;
            loadKeyFromTid(a, curKey);
            auto val = tree.getEG(curKey);
            std::cout << "search for key: " << num <<", with result tid: " << val << std::endl;

            return val;
        }

        void testInsertAndGetLG(){
            art_rowex::Tree tree(loadKeyFromTid);

            Key curKey;
            TID cur,next,a,b;
            TID a5 = genKVWithNUm(5);
            loadKeyFromTid(a5, curKey);
            tree.insertOrGetLG(curKey, a5, cur, next);
            //std::cout<< "----------a5: "<< a5 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a5);

            TID a5_1 = genKVWithNUm(5);
            loadKeyFromTid(a5_1, curKey);
            tree.insertOrGetLG(curKey, a5_1, cur, next);
            //std::cout<< "----------a5_1: "<< a5_1 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a5);

            TID a6 = genKVWithNUm(6);
            loadKeyFromTid(a6, curKey);
            tree.insertOrGetLG(curKey, a6, cur, next);
            //std::cout<< "----------a6: "<< a6 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a6);
        
            TID a2 = genKVWithNUm(2);
            loadKeyFromTid(a2, curKey);
            tree.insertOrGetLG(curKey, a2, cur, next);
            //std::cout<< "----------a2: "<< a2 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a2);
            assert(next == a5);

            TID a4 = genKVWithNUm(4);
            loadKeyFromTid(a4, curKey);
            tree.insertOrGetLG(curKey, a4, cur, next);
            //std::cout<< "----------a4: "<< a4 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a4);
            assert(next == a5);

            b = a6;
            for (int i = 0; i < 100; i++){
                a = genKVWithNUm(799 - i);
                loadKeyFromTid(a, curKey);
                tree.insertOrGetLG(curKey, a, cur, next);
                std::cout<< "----------a: "<< a << ", cur: " << cur << ", next: " << next <<std::endl;
                assert(cur == a);
                assert(next == b);
                b = a;
            }
        }

        void testNullorEmpty() {
            std::cout << "test case: key is null or empty!" << std::endl;
            art_rowex::Tree tree(loadKeyFromTid);

            printTID(searchWithNum(tree, 5));
            printTID(searchWithNum(tree, -1));
            Key curKey;
            TID cur,next,a,b;

            TID a55 = genKVWithNUm(55);
            loadKeyFromTid(a55, curKey);
            tree.insertOrGetLG(curKey, a55, cur, next);
            std::cout<< "----------a55: "<< a55 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a55);
            assert(next == 0);

            printTID(searchWithNum(tree, 5));
            printTID(searchWithNum(tree, -1));

            TID a_1 = genKVWithNUm(-1);
            loadKeyFromTid(a_1, curKey);
            tree.insertOrGetLG(curKey, a_1, cur, next);
            std::cout<< "----------a_1: "<< a_1 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a_1);
            assert(next == a55);

            printTID(searchWithNum(tree, 5));
            printTID(searchWithNum(tree, -1));

            TID a5 = genKVWithNUm(5);
            loadKeyFromTid(a5, curKey);
            tree.insertOrGetLG(curKey, a5, cur, next);
            std::cout<< "----------a5: "<< a5 << ", cur: " <<cur << ", next: " << next <<std::endl;
            assert(cur == a5);
            assert(next == a55);
        }

        void testEG() {
            std::cout << "test case: equal or greater!" << std::endl;
            art_rowex::Tree tree(loadKeyFromTid);

            insertWithNum(tree, -1);
            assertWithKey(searchWithNum(tree, -1), -1);
            assert(searchWithNum(tree, 1) == 0);
            insertWithNum(tree, 1);
            assertWithKey(searchWithNum(tree, 1), 1);
            insertWithNum(tree, 11);
            assertWithKey(searchWithNum(tree, 1), 1);
            assertWithKey(searchWithNum(tree, 11), 11);
            for (int i = 12; i <= 70; i++){
                insertWithNum(tree, i);
            }
            assertWithKey(searchWithNum(tree, -1), -1);
            assertWithKey(searchWithNum(tree, 2), 20);
            insertWithNum(tree, 2);
            assertWithKey(searchWithNum(tree, 2), 2);
            assert(searchWithNum(tree, 9) == 0);
            assertWithKey(searchWithNum(tree, 10), 11);
            assertWithKey(searchWithNum(tree, 3), 30);
            assertWithKey(searchWithNum(tree, 44), 44);
        }

        void testPathCompress() {
            std::cout << "test case: path compress!" << std::endl;
            art_rowex::Tree tree(loadKeyFromTid);

            insertWithNum(tree, 12345678);
            assertWithKey(searchWithNum(tree, 1234), 12345678);
            insertWithNum(tree, 1234);
            assertWithKey(searchWithNum(tree, 1233), 1234);
            assertWithKey(searchWithNum(tree, 12345), 12345678);
            insertWithNum(tree, 123457);
            assertWithKey(searchWithNum(tree, 123456), 12345678);
            assertWithKey(searchWithNum(tree, 1234569), 123457);
        }

        void multithreaded(uint64_t n, int treeType) {
            std::cout << "multi threaded:" << std::endl;

            //uint64_t n = std::atoll(argv[1]);
            TID* values  = new TID[n];

            // Generate values
            for (uint64_t i = 0; i < n; i++)
                values[i] = genKVWithNUm(i);
            if (treeType == 1)
                // dense, random
                std::random_shuffle(values, values + n);
            if (treeType == 2)
                // "pseudo-sparse" (the most-significant leaf bit gets lost)
                for (uint64_t i = 0; i < n; i++)
                    values[i] = (static_cast<uint64_t>(rand()) << 32) | static_cast<uint64_t>(rand());

            printf("operation,n,ops/s\n");
            art_rowex::Tree tree(loadKeyFromTid);

            // Build tree
            {
                auto starttime = std::chrono::system_clock::now();

                for (uint64_t i = 0; i < n; i++) {
                    Key key;
                    loadKeyFromTid(values[i], key);
                    TID cur, next;
                    tree.insertOrGetLG(key, values[i], cur, next);

                    auto val = tree.get(key);
                    if (val != values[i]) {
                        std::cout << "wrong key read: " << val << " expected:" << values[i] << std::endl;
                        key.dump();
                        throw;
                    }
                }
            
                auto duration = std::chrono::duration_cast<std::chrono::microseconds>(
                        std::chrono::system_clock::now() - starttime);
                printf("insert,%ld,%f\n", n, (n * 1.0) / duration.count());
            }

            {
                // Lookup
                auto starttime = std::chrono::system_clock::now();

                for (uint64_t i = 0; i < n; i++) {
                    Key key;
                    loadKeyFromTid(values[i], key);
                    auto val = tree.get(key);
                    if (val != values[i]) {
                        std::cout << "wrong key read: " << val << " expected:" << values[i] << std::endl;
                        key.dump();
                        throw;
                    }
                }
                auto duration = std::chrono::duration_cast<std::chrono::microseconds>(
                        std::chrono::system_clock::now() - starttime);
                printf("lookup,%ld,%f\n", n, (n * 1.0) / duration.count());
            }

            {
                auto starttime = std::chrono::system_clock::now();
                for (uint64_t i = 0; i < n; i++) {
                    Key key;
                    loadKeyFromTid(values[i], key);
                    tree.remove(key, values[i]);
                }
                auto duration = std::chrono::duration_cast<std::chrono::microseconds>(
                        std::chrono::system_clock::now() - starttime);
                printf("remove,%ld,%f\n", n, (n * 1.0) / duration.count());
            }
            delete[] values;
        }
    };

    class ROWEXTest : public testing::Test {
    };

    TEST_F(ROWEXTest, testNullorEmpty) {
        ROWEXExample rt;
        rt.testNullorEmpty();
        std::this_thread::sleep_for(std::chrono::seconds(5));
    }
    TEST_F(ROWEXTest, testInsertAndGetLG) {
        ROWEXExample rt;
        rt.testInsertAndGetLG();
        std::this_thread::sleep_for(std::chrono::seconds(5));
    }
    TEST_F(ROWEXTest, testEG) {
        ROWEXExample rt;
        rt.testEG();
    }
    TEST_F(ROWEXTest, testPathCompress) {
        ROWEXExample rt;
        rt.testPathCompress();
    }
    TEST_F(ROWEXTest, multithreaded) {
        ROWEXExample rt;
        rt.multithreaded(1000000, 1);
    }
}

int main(int argc, char **argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
    system("pause");
}
